#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n,m;
vector<int> map[1010][1010];
vector<int> flow[1010][1010];
int father[1010];
int father2[1010];
int inf=0xfffffff;
int SPFA(int vs,int vt)
{
    int w[1010],from,i,j;
    bool done[1010];
    fill(w,w+1010,inf);
    fill(done,done+1010,0);
    w[vs]=0;
    queue<int> q;
    q.push(vs);
    while(!q.empty())
    {
        from=q.front();
        q.pop();
        done[from]=0;
        for(i=0;i<=n+1;i++)
        {
        	for(j=0;j<flow[from][i].size();j++)
        	{
				if(flow[from][i][j]&&w[from]+map[from][i][j]<w[i])
				{
					w[i]=w[from]+map[from][i][j];
					father[i]=from;
					father2[i]=j;
					//cout<<father[i]<<" "<<i<<" "<<father2[i]<<endl;
					if(!done[i])
					{
						q.push(i);
						done[i]=1;
					}
				}
        	}
        }
    }
    return w[vt];
}
int f(int vs,int vt)
{
    int t,sum=0,i,j,n=2;
	fill(father,father+1010,-1);
    while(n--)
    {
        t=SPFA(vs,vt);
     //   cout<<t<<endl;
        //if(t==inf) break;
        for(i=vt;i!=vs;i=father[i])
        {
			cout<<father[i]<<" "<<i<<" "<<flow[father[i]][i][father2[i]]<<" "<<map[father[i]][i][father2[i]]<<endl;
			flow[father[i]][i][father2[i]]--;
			flow[i][father[i]][father2[i]]++;
			map[i][father[i]][father2[i]]=-map[father[i]][i][father2[i]];
			cout<<i<<" "<<father[i]<<" "<<map[i][father[i]][father2[i]]<<endl;
        }
        sum+=t;
    }
    return sum;
}
int main()
{
	int from,to,i,j,cost;
	while(cin>>n>>m)
	{
		while(m--)
		{
			scanf("%d%d%d",&from,&to,&cost);
			flow[from][to].push_back(1);
			flow[to][from].push_back(1);
			map[from][to].push_back(cost);
			map[to][from].push_back(cost);
		}
		flow[n][n+1].push_back(2);
		flow[n+1][n].push_back(0);
		map[n][n+1].push_back(0);
		map[n+1][n].push_back(0);
		flow[1][0].push_back(0);
		map[1][0].push_back(0);
		flow[0][1].push_back(2);
		map[0][1].push_back(0);
		cout<<f(0,n+1)<<endl;
        while(1);
	}
	return 0;
}
